#include <stdio.h>
#include <stdlib.h>

typedef int ElemSet; /* 默认元素为整型 */
typedef struct RecordNode *Records;
struct RecordNode {
    ElemSet key; /* 关键字 */
    /* 其他属性由用户自定义 */
};

typedef Records TElemSet;
typedef struct TreapNode *Position; /* 树结点指针是元素的位置 */
typedef struct TreapNode *Treap;
struct TreapNode {
    TElemSet data; /* 数据元素 */
    int priority; /* 优先级 */
    Treap left; /* 左孩子指针 */
    Treap right; /* 右孩子指针 */
};
#define NIL NULL

void Visit(Treap tree) {
    printf("%d:%d\n", tree->data->key, tree->priority);
}

void PreOrder(Treap tree) {
    if (tree != NIL) {
        Visit(tree);
        PreOrder(tree->left);
        PreOrder(tree->right);
    }
}

Position RRotate(Position x) {
    Position y;

    y = x->left; /* 这里保证y不是空结点 */
    x->left = y->right;
    y->right = x;

    return y;
}

Position LRotate(Position x) {
    Position y;

    y = x->right; /* 这里保证y不是空结点 */
    x->right = y->left;
    y->left = x;

    return y;
}

/* 算法12-10 树堆的插入 InsertTreap(treap, x) */
Treap InsertTreap(Treap treap, Records x) {
    if (treap ==
                NIL) { /* 若是空树，为x创建新的树根结点，priority取随机数rand() */
        treap = (Treap)malloc(sizeof(struct TreapNode));
        treap->data = x;
        treap->priority = rand();
        treap->left = treap->right = NIL;
    } else { /* 若不是空树 */
        if (x->key < treap->data->key) {
            treap->left = InsertTreap(treap->left, x);
            if (treap->left->priority < treap->priority) { /* 左孩子优先级高 */
                treap = RRotate(treap);
            }
        } else if (x->key > treap->data->key) {
            treap->right = InsertTreap(treap->right, x);
            if (treap->right->priority < treap->priority) { /* 右孩子优先级高 */
                treap = LRotate(treap);
            }
        } /* x.key = treap.data.key 时不重复插入 */
    }
    return treap;
}
/* 算法12-10 结束 */

int main(void) {
    Treap treap;
    Records x;
    int n, i;

    treap = NULL;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        x = (Records)malloc(sizeof(struct RecordNode));
        scanf("%d", &x->key);
        treap = InsertTreap(treap, x);
    }
    PreOrder(treap);

    return 0;
}